Online storage of data (e.g., Amazon's S3 storage service) is becoming increasingly popular for both corporations and consumers. Clients can create virtual drives consisting of online storage units that are operated by remote and geographically dispersed servers. In addition to being a convenient solution for data archiving or backups, remote storage allows for load-balanced distributed data management (e.g., database outsourcing). Large data volumes can become available to end applications through high-bandwidth connections to the data-hosting servers, which can rapidly answer queries arriving at high rates. In such a manner, data sources need to be online only when they wish to update their published data.
In several settings, the ability to check the integrity of remotely stored data is an important security property. Namely, one would like to detect both data corruption caused by a faulty server (e.g., because of hardware issues or software errors) and data tampering performed by an attacker that compromises the server (e.g., deliberate deletion or modification of files). Without some kind of verification mechanism, errors and attacks cannot be detected, no matter what trust relations the client and the server may a priori share.
Hash tables are fundamental data structures that optimally answer membership queries. Suppose a client stores n elements in a hash table that is outsourced at a remote server. Authenticating the hash table functionality, i.e., verifying the correctness of queries answered by the server and ensuring the integrity of the stored data, is crucial because the server, lying outside the administrative control of the client, can be malicious.